#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/**
 * 给定一个整数数组 nums，找出一个连续子数组（至少包含一个元素），使得该子数组的和最大，并返回这个最大值。

示例
cpp
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 子数组 [4,-1,2,1] 的和为 6。
动态规划解法（Kadane's Algorithm）
这是最经典的解法，时间复杂度为 O(n)，空间复杂度为 O(1)。

状态定义
dp[i] 表示以第 i 个元素结尾的最大子数组和
状态转移方程
cpp
dp[i] = max(nums[i], dp[i - 1] + nums[i])
要么单独选当前元素，要么加上前面的结果
 */
int maxSubArray(vector<int>& nums) {
    int n = nums.size();
    int current_sum = 0;
    int max_sum = INT_MIN;

    for (int i = 0; i < n; ++i) {
        current_sum = max(nums[i], current_sum + nums[i]);
        max_sum = max(max_sum, current_sum);
    }

    return max_sum;
}

int main() {
    vector<int> nums = {-2,1,-3,4,-1,2,1,-5,4};
    cout << "最大子数组和: " << maxSubArray(nums) << endl;
    return 0;
}